Kleitman–Wang algorithms
The Kleitman–Wang algorithms are two different algorithms in graph theory solving the digraph realization problem, i.e. the question if there exists for a finite list of nonnegative integer pairs a simple directed graph such that its degree sequence is exactly this list. For a positive answer the list of integer pairs is called digraphic. Both algorithms construct a special solution if one exists or prove that one cannot find a positive answer. These constructions are based on recursive algorithms. Kleitman and Wang [1] gave these algorithms in 1973.
Kleitman–Wang algorithm (arbitrary choice of pairs)
The algorithm is based on the following theorem.
Let [math]\displaystyle{ S=((a_1,b_1),\dots,(a_n,b_n)) }[/math] be a finite list of nonnegative integers that is in nonincreasing lexicographical order and let [math]\displaystyle{ (a_i,b_i) }[/math] be a pair of nonnegative integers with [math]\displaystyle{ b_i \gt 0 }[/math]. List [math]\displaystyle{ S }[/math] is digraphic if and only if the finite list [math]\displaystyle{ S'=((a_1-1,b_1),\dots,(a_{b_i-1}-1,b_{b_i-1}),(a_{b_i},0),(a_{b_i+1},b_{b_i+1}),(a_{b_i+2},b_{b_i+2}),\dots,(a_n,b_n)) }[/math] has nonnegative integer pairs and is digraphic.
Note that the pair [math]\displaystyle{ (a_i,b_i) }[/math] is arbitrarily with the exception of pairs [math]\displaystyle{ (a_j,0) }[/math]. If the given list [math]\displaystyle{ S }[/math] digraphic then the theorem will be applied at most [math]\displaystyle{ n }[/math] times setting in each further step [math]\displaystyle{ S:=S' }[/math]. This process ends when the whole list [math]\displaystyle{ S' }[/math] consists of [math]\displaystyle{ (0,0) }[/math] pairs. In each step of the algorithm one constructs the arcs of a digraph with vertices [math]\displaystyle{ v_1,\dots,v_n }[/math], i.e. if it is possible to reduce the list [math]\displaystyle{ S }[/math] to [math]\displaystyle{ S' }[/math], then we add arcs [math]\displaystyle{ (v_i,v_1),(v_i,v_2),\dots,(v_{i},v_{b_i-1}),(v_i,v_{b_i+1}) }[/math]. When the list [math]\displaystyle{ S }[/math] cannot be reduced to a list [math]\displaystyle{ S' }[/math] of nonnegative integer pairs in any step of this approach, the theorem proves that the list [math]\displaystyle{ S }[/math] from the beginning is not digraphic.
Kleitman–Wang algorithm (maximum choice of a pair)
The algorithm is based on the following theorem.
Let [math]\displaystyle{ S=((a_1,b_1),\dots,(a_n,b_n)) }[/math] be a finite list of nonnegative integers such that [math]\displaystyle{ a_1 \geq a_2 \geq \cdots \geq a_n }[/math] and let [math]\displaystyle{ (a_i,b_i) }[/math] be a pair such that [math]\displaystyle{ (b_i,a_i) }[/math] is maximal with respect to the lexicographical order under all pairs [math]\displaystyle{ (b_1,a_1),\dots,(b_n,a_n) }[/math]. List [math]\displaystyle{ S }[/math] is digraphic if and only if the finite list [math]\displaystyle{ S'=((a_1-1,b_1),\cdots,(a_{b_i-1}-1,b_{b_i-1}),(a_{b_i},0),(a_{b_i+1},b_{b_i+1}),(a_{b_i+2},b_{b_i+2}),\dots,(a_n,b_n)) }[/math] has nonnegative integer pairs and is digraphic.
Note that the list [math]\displaystyle{ S }[/math] must not be in lexicographical order as in the first version. If the given list [math]\displaystyle{ S }[/math] is digraphic, then the theorem will be applied at most [math]\displaystyle{ n }[/math] times, setting in each further step [math]\displaystyle{ S:=S' }[/math]. This process ends when the whole list [math]\displaystyle{ S' }[/math] consists of [math]\displaystyle{ (0,0) }[/math] pairs. In each step of the algorithm, one constructs the arcs of a digraph with vertices [math]\displaystyle{ v_1,\dots,v_n }[/math], i.e. if it is possible to reduce the list [math]\displaystyle{ S }[/math] to [math]\displaystyle{ S' }[/math], then one adds arcs [math]\displaystyle{ (v_i,v_1),(v_i,v_2),\dots,(v_i,v_{b_i-1}),(v_i,v_{b_i+1}) }[/math]. When the list [math]\displaystyle{ S }[/math] cannot be reduced to a list [math]\displaystyle{ S' }[/math] of nonnegative integer pairs in any step of this approach, the theorem proves that the list [math]\displaystyle{ S }[/math] from the beginning is not digraphic.
See also
References
- Kleitman, D. J.; Wang, D. L. (1973), "Algorithms for constructing graphs and digraphs with given valences and factors", Discrete Mathematics 6: 79–88, doi:10.1016/0012-365x(73)90037-x
- ↑ (Kleitman Wang)
 |  |
